package com.algorithm.递归;

public class 斐波那契数列 {
    /**
     * 最烂的写法
     *
     * @param n
     * @return
     */
    public int fib0(int n) {
        if (n <= 2) return 1;
        return fib0(n - 1) + (n - 2);
    }

    /**
     * 优化后的写法
     *
     * @param n
     * @return
     */
    public int fib1(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        return fib1(n, array);
    }
    public int fib1(int n, int[] array) {
        if (array[n] == 0) {
            array[n] = fib1(n - 1, array) + fib1(n - 2, array);
        }
        return array[n];
    }

    /**
     * 第二种优化方式，去掉递归
     *
     * @param n
     * @return
     */
    public int fib2(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        for (int i = 3; i < n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

    /**
     * 滚动数组优化
     *
     * @param n
     * @return
     */
    public int fib3(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i < n; i++) {
            array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
        }
        return array[n % 2];
    }

    /**
     * 优化 fib3 中的取模运算。所有 %2 的操作都可以用 &1 来代替，效率更高
     *
     * @param n
     * @return
     */
    public int fib4(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i < n; i++) {
            array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
        }
        return array[n & 1];
    }

    /**
     * 不使用数组优化
     *
     * @param n
     * @return
     */
    public int fib5(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        while (n-- > 1) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * 使用特征方程
     *
     * @param n
     * @return
     */
    public int fib6(int n) {
        double c = Math.sqrt(5);
        return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
    }
}
